package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/6/14 21:26
 */
public class isSubtree {

    static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int val) {
            this.value = val;
        }
    }

    public boolean isSubtree(Node t1, Node t2) {
        String str1 = serialByPre(t1);
        String str2 = serialByPre(t2);
        return KMP(str1, str2) != -1;
    }

    private String serialByPre(Node head) {
        if (head == null) {
            return "#!";
        }
        String res = head.value + "#";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    // KMP算法没有理解，暂时不写
    private int KMP(String str1, String str2) {
        return -1;
    }

}
